Virtual Private LAN Services (VPLS), although a relatively new technology, is already being used by service providers to aggregate services for delivery to residential and enterprise customers. These services include broadcast multimedia such as Digital TV and Video on Demand.
VPLS, also known as Transparent LAN Service (TLS) or E-LAN service, is a layer 2 multipoint Virtual Private Network (VPN) that allows multiple sites to be connected in a single bridged domain over a provider managed IP/MPLS network. All customer sites in VPLS instance appear to be on the same LAN regardless of their location.
A VPLS-capable network consists of Customer Edges (CE), Provider Edges (PE) and a core MPLS network. The CE device is a router or switch located at the customer's premises and can either be owned by the customer or the service provider. It is connected to the PE via an Attachment Circuit (AC). The PE device is where all the VPN intelligence resides, where the VPLS originates and terminates and where all the necessary tunnels are set up to connect to all other PEs. The core MPLS network interconnects the PEs; it does not really participate in the VPN functionality. Traffic is simply switched based on the MPLS labels.
The basis of VPLS is the full mesh of MPLS tunnels (outer tunnels) that are set up between all the participating PEs in the VPN service. For every VPLS instance, a full mesh of inner tunnels also called pseudo wires (PW), is created between all the PEs that participate in the VPLS instance. A PW consists of a pair of point to point, single hop, unidirectional Label Switched Paths (LSP) in opposite directions, each identified by a PW label.
To prevent forward loops, the Split Horizon rule is used. In the VPLS context, this rule basically implies that a PE must never send a packet on a PW if that packet has been received from a PW. This ensures that traffic cannot form a loop over the backbone network using PWs. The fact that there is always a full mesh of PWs between the PE devices ensures that every destination within the VPLS will be reached by a broadcast packet.
Any new or emerging technology must be capable of providing as good as or better service than the technology it seeks to replace. Thus, for VPLS technology to find acceptance in the multimedia broadcast field it must be able to provide reliable and resilient service at a comparable cost to existing services. As a consequence there has been considerable effort devoted to finding architectures which allow VPLS to provide the required services in a cost effective and efficient manner.
The following discussion relates to efforts involving redundant trees which have evolved to support resiliency in a multicast network. These schemes can be classified into two categories: the static scheme which uses a pre-computed back up path, and a dynamic scheme that computes the back up path on the fly.
The algorithms in the static schemes build a primary and a backup tree at the same time. In a publication by M. Kodialem and T. Lakshman, “Dynamic routing of bandwidth guaranteed multicasts with failure backup”, Proceedings of IEEE INFOCOM, June 2002, an algorithm is described that minimizes the bandwidth that is used by the primary and the backup paths. The algorithm selects every member of the group, starting with the source (in the case of shortest path trees) or center (in the case of center-based trees). For each member, two disjoint paths from the source (or center) to this member are computed. One path is inserted in the primary tree and the other in the backup tree. Bandwidth used by the trees is minimized. However, since a backup path protects the tree for all possible link failures, the total bandwidth that should be reserved for the backup tree is at least the same as the bandwidth reserved for the primary tree. Similar approaches are proposed by Alon Itai and Michael Rodeh, in “The multi-tree approach to reliability in distributed networks”, IEEE Symposium on Foundations of Computer Science, pages 137-147, 1984 and by M. Médard, S. Finn, R. Barry, and R. Gallager, in “Redundant trees for preplanned recovery in arbitrary vertex-redundant or edge-redundant graphs”, IEEE/ACM Transactions on Networking, 7(5):641-652, 1999 where the transmission from source to destination node is accomplished by sending the packet from source to the root node, and then from root to the destination node. If there is no link or node failure, the transmission is performed on the primary tree. When a single node or link failure happens, the traffic affected by the failure uses the backup tree. In the Médard et al publication, the algorithm constructs two directed Spanning trees rooted at source node. One of them is used as the working tree, and the other spanning tree is used for failure recovery.
In an article by Y. F. Wang and R.-F. Chan, entitled “Self-healing on ATM multicast tree”, IEICE Transaction on Communication, E81-B(8):590-598, August 1998, an online (dynamic) mechanism is introduced to repair ATM multicast routing tree. When a failure happens, the multicast routing tree is split into two smaller trees. One of these smaller trees contains the source or center of the original tree and the other sub-tree is the tree rooted at the switch downstream of the failed link. That switch sends a failure notification message that contains its unique switch identifier to all of its neighbors. Each neighbor forwards the notification message to its own neighbors and so on, thus flooding the network with the notification message. The first switch of the other sub-tree that receives the notification message replies and a backup path is set up between the two switches. This backup path is inserted in the multicast routing tree, and the tree is repaired.
The pre-planned recovery schemes presented in prior arts focus on either “spanning tree” redundancy, or “shortest path tree” redundancy.
In related U.S. patent application Ser. No. 11/060,465 filed Feb. 18, 2005 a minimum cost tree architecture is proposed in order to broadcast multimedia services (Digital TV, Video on Demand) over VPLS networks. Although the tree structure in the prior application provides significant bandwidth savings compared to the traditional VPLS architecture based on full/partial mesh connectivity between PE routers, the tree structure is not resilient, i.e. a failure in the tree could disconnect many nodes, and even disrupt the whole communications. The contents of U.S. application Ser. No. 11/060,465 are incorporated herein by reference.
None of prior art, of which the inventors are aware, provides redundancy for minimum-cost (Steiner) multicast tree, which is the subject of this invention. Moreover, none of them discusses the steps as to how to switch over traffic from a failed tree to a backup tree.